package com.shuang.tree22;

import java.util.LinkedList;
import java.util.Queue;

public class IsSameTree {

    public boolean isSameTree(TreeNode p, TreeNode q) {

        // //判断根节点情况
        // if (p == null && q == null) {
        //     return true;
        // }

        // if (p == null || q == null || p.val != q.val) {
        //     return false;
        // }

//        //根据队列实现 判断两颗树是否一样
//        Queue<TreeNode> que = new LinkedList<>();
//
//        que.offer(p);
//        que.offer(q);
//
//        while (!que.isEmpty()) {
//            //弹出左树节点
//            TreeNode leftNode = que.poll();
//            //弹出右树节点
//            TreeNode rightNode = que.poll();
//
//            if (leftNode == null && rightNode == null) {
//                continue;
//            }
//
//            if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) {
//                return false;
//            }
//
//            que.offer(leftNode.left);
//            que.offer(rightNode.left);
//            que.offer(leftNode.right);
//            que.offer(rightNode.right);
//        }
//
//        return true;

        //递归实现

        //判断节点情况
        if (p == null && q == null) {
            return true;
        }

        if (p == null || q == null || p.val != q.val) {
            return false;
        }

        //节点都不为空 且值相等 接着往下走 相当于后序 处理左 右 中的顺序
        boolean leftSame = isSameTree(p.left, q.left);
        boolean rightSame = isSameTree(p.right, q.right);
        boolean result = leftSame && rightSame;

        return result;

    }
}
